Enumeration of Road Network Plans

Memory limit: 64 MB

Byteman is going for a car trip around Byteland, but he is unfortunately unable to buy a map of the country. His friends told him about some properties of the bytean road network:

• There are cities in Byteland, numbered from to .
• Each road is bidirectional and connects two different cities.
• Each pair of different cities is connected by exactly one path, consisting of one or more roads, on which no city appears more than once.
• The longest path, on which no city appears more than once, consists of roads.

Using information that he managed to collect, Byteman is going to try to reconstruct the road map of Byteland. Byteman would not like to work on it too much, so he would like to know the number of different road network plans satisfying the given conditions. During comparison of plans Byteman does not take exact locations of cities into consideration, but only the plan of connections; moreover, he is not interested in particular city numbers. In other words, Byteman considers two plans the same if and only if there exists a one-to-one mapping from cities of one plan to the cities of the other one, such that if cities and are connected by a road on the first plan then their equivalents and are also connected by a road on the second plan.

Task

Write a program that:

• reads numbers , and from the standard input,
• computes the number of different road network plans, that are consistent with information that Byteman managed to collect, modulo ,
• writes the result to the standard output.

Input

The first and only line of the input contains three integers , and (, , , is a prime number), separated with single spaces.

Output

The first and only line of output should contain a single integer - the remainder of the division by of the number of different plans that are consistent with conditions known to Byteman.

Example

For the input data:

6 3 13

the correct result is:

2

Task author: Jakub Radoszewski.